/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 combat_obstruction_finder.h

	$Header: /heroes4/combat_obstruction_finder.h $

	$NoKeywords: $

 ************************************************************************/
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "combat_obstruction_finder.h"

#include "battlefield.h"
#include "combat_footprint.h"
#include "combat_object_base.h"
#include "enum_operations.h"
// ---------------------------------------------------------------
// abstract object for finding obstructions
// ---------------------------------------------------------------
namespace
{
	class t_potential_creature : public t_combat_object_base
	{
	public:
		t_potential_creature( int size );

		virtual int  get_footprint_size() const;
		virtual bool is_creature() const;
	protected:
		int m_size;
	};
};

// ---------------------------------------------------------------
// abstract object for finding obstructions
// ---------------------------------------------------------------
inline t_potential_creature::t_potential_creature( int size )
{
	m_size = size;
}

// ---------------------------------------------------------------
// abstract object for finding obstructions
// ---------------------------------------------------------------
int t_potential_creature::get_footprint_size() const
{
	return m_size;
}

bool t_potential_creature::is_creature() const
{
	return true;
}

// ---------------------------------------------------------------
// class to find obstructions in combat map
// ---------------------------------------------------------------
t_combat_obstruction_finder::t_combat_obstruction_finder( t_battlefield& battlefield,
														  bool has_castle )
						   : t_combat_path_finder_base( battlefield.get_size() ),
						     m_battlefield( battlefield )
{
	m_has_castle = has_castle;
}

static int const k_castle_row = 54;
// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
void t_combat_obstruction_finder::initialize()
{
	if (m_initialized)
		return;

	// mark all points that can be entered by a 7x7 creature
	m_initialized = true;

	t_battlefield&					battlefield = m_battlefield;
	t_combat_path_blockage			blockage;
	t_combat_footprint const&       footprint = get_combat_footprint( 7 );

	blockage.blocked = false;
	blockage.in_tower = false;
	blockage.forbidden = false;
	blockage.has_wall = false;

	t_combat_path_blockage_map map( battlefield.get_size(),
						            k_battlefield_cell_height,
					                k_battlefield_logical_view_size,
									blockage );

	map.mark_obstacles( battlefield );
	clear_map( battlefield, map, footprint );

	// find point to start seed
	t_map_point_2d      point;
	int                 row_end;
	t_combat_path_data* ptr;

	// find the first point that can be entered
	point.row = m_data.get_size();
	while (point.row--)
	{
		if (m_has_castle && point.row < k_castle_row)
			break;
		point.column = m_data.get_row_start( point.row );
		row_end = m_data.get_row_end( point.row );
		ptr = &m_data.get( point );
		while (point.column < row_end)
		{
			if (!ptr->blocked)
			{
				push_first_point( point );
				return;
			}
			ptr++;
			point.column++;
		}
	}
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
void t_combat_obstruction_finder::generate_paths()
{
	initialize();

	t_combat_path_point point;
	t_direction         direction;

	if (m_open_points.empty())
		return;

	// for each open point, check adjacent points
	while (!m_open_points.empty())
	{
		point = m_open_points.top();
		m_open_points.pop();
		for (direction = t_direction(0); direction < k_direction_count; enum_incr( direction ))
		{
			t_combat_path_point new_point( point + get_direction_offset( direction ) );
			
			if (!m_data.is_valid( new_point ))
				continue;

			if (m_has_castle && new_point.row < k_castle_row)
				continue;

			// move cost is zero unless we have had to traverse an obstruction
			// to get here
			int move_cost = 0;

			t_combat_path_data const& cell = m_data.get( new_point );

			if (cell.off_map)
				continue;
			if (cell.forbidden)
				continue;

			if (cell.blocked || point.move_cost > 0)
			{
				move_cost = 2;
			}
			// diagonals cost 50% more (approximation of 1.414)
			if (direction & 1)
				move_cost += move_cost >> 1;

			new_point.blocked = cell.blocked;
			new_point.off_map = cell.off_map;
			new_point.forbidden = false;

			new_point.move_cost = point.move_cost + move_cost;
			new_point.flight_cost = 0;
			new_point.visited = true;
			new_point.reachable = !cell.blocked;
			new_point.nearest_point = new_point;
			new_point.last_point = point;
			new_point.direction = direction;
			push( new_point );
		}
	}
	// mark all points that will be occupied by a valid destination
	mark_reachable_points( get_combat_footprint( 7 ) );
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// find the best point to clear a path from in order to touch a point
// ---------------------------------------------------------------
t_map_point_2d t_combat_obstruction_finder::find_closest_point( t_map_point_2d const& start ) const
{
	bool					  best_point_valid = false;
	t_map_point_2d            origin;
	t_map_point_2d            best_point;
	int						  best_distance;
	t_combat_footprint const& footprint = get_combat_footprint( 4 );
	t_map_point_2d            offset;
	t_map_point_2d            new_point;
	t_map_point_2d            nearest_point;
	int const*				  ptr = footprint.get();
	t_combat_path_data const* data;

	// assumes target is 2x2, and that the minimum attack distance is 1,
	// so the footprint is 4x4
	origin.column = start.column - 1;
	origin.row    = start.row - 1;
	best_point = start;
	for (offset.row = 0; offset.row < 4; offset.row++)
	{
		for (offset.column = 0; offset.column < 4; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = origin + offset;
			if (!m_data.is_valid( new_point ))
				continue;
			// examine this point - will it be occupied by part of a 7x7 destination?
			nearest_point = new_point;
			data = &m_data.get( new_point );
			if (data->reachable)
			{
				nearest_point = data->nearest_point;
				data = &m_data.get( nearest_point );
			}
			if (data->off_map || data->forbidden)
				continue;
			// check if we already have a point that is as good
			if (best_point_valid && best_distance <= data->move_cost)
				continue;
			best_point_valid = true;
			best_point = nearest_point;
			best_distance = data->move_cost;
			if (best_distance == 0)
				return best_point;
		}
	}
	return best_point;
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// find some point, any point, which needs to be have a path cleared
// ---------------------------------------------------------------
bool t_combat_obstruction_finder::find_obstruction( t_map_point_2d& result ) 
{
	// find an obstructed point
	t_potential_creature creature(2);
	t_map_point_2d      point;
	t_map_point_2d      nearby_point;
	int                 row_end;
	t_combat_path_data* ptr;

	generate_paths();
	point.row = m_data.get_size();
	while (point.row--)
	{
		point.column = m_data.get_row_start( point.row );
		row_end = m_data.get_row_end( point.row );
		ptr = &m_data.get( point );
		while (point.column < row_end)
		{
			if ((ptr->move_cost > 0 || ptr->off_map || ptr->forbidden)
				&& m_battlefield.can_place( creature, point ))
			{
				result = find_closest_point( point );
				if (m_data.get( result ).move_cost > 0)
					return true;
			}
			ptr++;
			point.column++;
		}
	}
	return false;
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// find closest connected point
// ---------------------------------------------------------------
void t_combat_obstruction_finder::get_path( t_map_point_2d const&	dest,
										    t_combat_path&			path )
{
	t_map_point_2d result = dest;

	generate_paths();

	t_combat_path_data const* data = &m_data.get( dest );

	assert( data->visited );
	path.push_back( t_combat_path_point( dest ));
	while ( data->move_cost > 0 )
	{
		result = data->last_point;
		path.push_back( t_combat_path_point( result ) );
		data = &m_data.get( result );
	}
}

// ---------------------------------------------------------------
// pathfinder for combat obstacles
// start a new search, re-check blocked status
// ---------------------------------------------------------------
void t_combat_obstruction_finder::seed( t_map_point_2d const& new_point )
{
	push_first_point( new_point );

	// clear array
	t_map_point_2d       point;
	int                  row_end;
	t_combat_path_data*  ptr;
	t_potential_creature object( 7 );

	point.row = m_data.get_size();
	while (point.row--)
	{
		point.column = m_data.get_row_start( point.row );
		row_end = m_data.get_row_end( point.row );
		ptr = &m_data.get( point );
		while (point.column < row_end)
		{
			if (!ptr->off_map && !ptr->forbidden && ptr->blocked)
				ptr->blocked = !m_battlefield.can_place( object, point );
			ptr++;
			point.column++;
		}
	}
}
